package org.gpf;


public class Max2 {

	/**
	 * 求得数组中的最大值和次大值【累计比较次数是2n-3】
	 * @param arr 数组
	 * @param start 数组起始下标
	 * @param end 数组结束下标
	 */
	/*private static int[] max2(int arr[], int start, int end) {

		int[] temp = new int[2];

		int x1 = start, x2 = start;
		// 扫描arr[start]~arr[end-1]找出arr[x1]
		for (int i = start + 1; i < end; i++) {
			if (arr[i] > arr[x1]) {					// 找出x1需要比较n-1次
				x1 = i;
			}
		}
		// 扫描除了arr[x1]以外的区间，找出arr[x2]，需要两次循环
		for (int i = start + 1; i < x1; i++) {
			if (arr[i] > arr[x2]) {
				x2 = i;
			}
		}											// 找出x2需要比较n-2次
		for (int i = x1 + 1; i < end; i++) {
			if (arr[i] > arr[x2]) {
				x2 = i;
			}
		}
		temp[0] = arr[x1];
		temp[1] = arr[x2];
		return temp;
	}*/
	
	private static int[] max2(int arr[], int start, int end) {

		int x1, x2;
		// 初始化，经过这样一来数组开始的两个元素中必定x1是最大元素，x2是次大元素 
		if (arr[x1 = start] < arr[x2 = start + 1]) {  // 1次比较
			int temp = x1;
			x1 = x2;
			x2 = temp;
		}
		
		for (int i = start + 2; i < end; i++) {
			// 只有当arr[i]>arr[x2]的时候，只有当arr[i]胜出了arr[x2],才将x2更新为i，用更新后的数值与最大的arr[x1]比较，并在确实有必要的时候更新x1
			if (arr[x2] < arr[i] && arr[x1] < arr[x2 = i]) { // 注意：当arr[x2]<arr[i]的时候实际上arr[x2]的值已经更新了，因为后面要执行判断语句的时候赋值了
				int temp = x1;
				x1 = x2;
				x2 = temp;
			}
		}
		return new int[] { arr[x1], arr[x2] };
	}
	
	public static void main(String[] args) {

		int[] arr = {1,2,5,8,-8,-9,22,99,882,25};
		int[] temp = max2(arr, 0, arr.length);
		System.out.println("最大数：" + temp[0]);
		System.out.println("次大数：" + temp[1]);
	}

}
